#include <stdio.h>

#define NUM 3
#define N 8

void back_circle();
void back_circle_fixed();
void back_circle_struct();

typedef struct person{
    int n;
    int num;
    struct person *nextp;
}person;


/**
 * 题目：有n个人围成一圈，顺序排号。从第一个人开始报数（从1到3报数），
 *      凡报到3的人退出圈子，问最后留下的是原来第几号的那位。
*/
int main(int argc, char const *argv[])
{
    // back_circle();
    // back_circle_fixed();
    back_circle_struct();

    return 0;
}

void back_circle()
{
    int n;
    printf("请输入人数：");
    scanf("%d", &n);
    int nums[n];
    int *p;
    p = nums;
    for(int i = 0; i < n; i++)
        *(p+i) = i+1;
    
    int m,j,k;
    m = n;
    k = 0;
    j = 0;
    while (m>1)
    {
        if(*(p+j)!=0)
            k++;
        
        if(k==NUM)
        {
            *(p+j)=0;
            k = 0;
            m--;
        }
        j++;

        if(j == n)
            j = 0;
    }
    
    for (int i = 0; i < n; i++)
    {
        if (nums[i] != 0)
        {
            printf("最后留下的人的编号是： %d\n", nums[i]);
        }
        
    }
}

void back_circle_fixed()
{
    int i, j, k, str[N] = {0};
    
    for(k=0,i=0,j=N; j>0; i++)
    {
        if(i>=N)    //在圈中循环
            i%=N;
        
        if(0==str[i])
        {
            if(++k % 3 == 0)
            {
                str[i] = 1;
                --j;
            }
        }
    }
    printf("最后留下的是:%d\n", i);
    //getchar();
}

void back_circle_struct()
{
    int j,count;
    person *p;
    person link[N];
    
    for(int i=0; i<N; i++)
    {
        link[i].n = i+1;
        link[i].num = 1;
        if(i == N - 1)
            link[i].nextp=&(link[0]);
        else
            link[i].nextp=&(link[i+1]);
    }

    count=0;
    p=link;
    while (count<N-1)
    {
        j = 1;
        while (j != 3)
        {
            if (p->num)
                j++;
 
            p = p->nextp;
            while(!p->num)
                p=p->nextp;
        }
        
        p->num=0;
        count++;
    }
    
    for(int i=0; i<N; i++)
    {
        if(link[i].num!=0)
            printf("最后留下的是:%d\n", link[i].n);
    }
}